package cn.itcast.algorithm;

/**
 * 爬楼梯问题
 * N阶梯楼梯  只能一次走一步或者一次走2步 问有多少种走法
 * create by zhangtian3 on 2019/4/8
 */
public class ClimbStair {
    /**
     * 爬楼梯问题-递归实现
     * @param n
     * @return
     */
    public static long recursionStair(int n){
        if (n <= 0){
            return 0 ;
        }

        if (n ==1) {
            return 1 ;
        }

        if (n == 2) {
            return 2;
        }

        return recursionStair(n-1) + recursionStair(n -2) ;
    }

    /**
     * 使用循环代替递归
     * @param n
     * @return
     */
    public static long recursionStairCycly(int n){
        if (n <= 0) {
            return 0 ;
        }

        long[] arr = new long[n + 1] ;
        arr[0] = 1 ;
        arr[1] = 2 ;

        for(int i = 2; i < n; i++){
            arr[i] = arr[i-1] + arr[i-2] ;
        }

        return arr[n-1] ;
    }

    /**
     * 条件变化：可以走一步  两步  三步
     * 使用动态规划
     * @param n
     * @return
     */
    public static long recursionStairCycly3(int n){
        if (n <= 0) {
            return 0 ;
        }

        long[] arr = new long[n + 2] ;
        arr[0] = 1 ;
        arr[1] = 2 ;
        arr[2] = 4 ;

        for(int i = 3; i < n; i++){
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3] ;
        }

        return arr[n-1] ;
    }

    /**
     * 爬楼梯 同样数组实现
     * @param n
     * @return
     */
    public static long recursionStair2Cycly(int n){
        if (n <= 0){
            return 0 ;
        }

        if (n ==1) {
            return 1 ;
        }

        if (n == 2) {
            return 2;
        }

        long total = 0 ;
        long pre1Value = 1 ;
        long pre2Value = 2 ;

        for(int i = 2; i < n; i++){
            total = pre1Value + pre2Value ;
            pre1Value = pre2Value ;
            pre2Value = total ;
        }

        return total ;
    }
}
